package LeetCode刷题;

import java.util.Arrays;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-10-02 16:55
 * @description: Functions of this class is
 * 官方解法：（贪心+二分查找）
 *
 *
 *
 **/
public class NoNoNo动态规划最长递增子序列 {
    public static void main(String[] args) {

    }
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 1) {
            return 1;
        }
        int maxLen[] = new int[nums.length];
        Arrays.fill(maxLen, 1);//以每一个元素结尾的子序列长度都初始化为1（其前面肯定有一个元素）
        int ans = 1;//答案初始化为1
        for (int i = 1; i < nums.length; i++) {//从第二个元素开始算起
            for (int j = 0; j < i; j++) {//算当前元素前面的那些子序列的最长长度为多少
                if (nums[j] < nums[i]) {//如果前面的哪一个元素小于当前元素，则开始进行动态规划
                    //即当前元素的最长子序列=当前元素的最长子序列and现在遍历到的在当前元素之前的这个元素的最长子序列长度+1（当前元素）
                    maxLen[i] = Math.max(maxLen[i], maxLen[j] + 1);
                }
            }
            ans = Math.max(ans, maxLen[i]);//然后找出最长的子序列长度
        }
        return ans;
    }
}